package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 邓大帅
 * Date: 2024-01-18
 * Time: 9:33
 */
//二叉搜索树
public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root = null;
    public void createTree() {
        TreeNode node1 = new TreeNode(80);
        TreeNode node2 = new TreeNode(30);
        TreeNode node3 = new TreeNode(100);
        TreeNode node4 = new TreeNode(20);
        TreeNode node5 = new TreeNode(50);
        TreeNode node6 = new TreeNode(90);
        TreeNode node7 = new TreeNode(110);
        TreeNode node8 = new TreeNode(95);
        TreeNode node9 = new TreeNode(115);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node6.right = node8;
        node7.right = node9;
        root = node1;
    }
    //查找指定值
    public TreeNode find(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (val > cur.val) {
                cur = cur.right;
            }else if (val < cur.val) {
                cur = cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }
    //插入数据
    public void insert(int val) {
        if (root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode node = new TreeNode(val);
        TreeNode cur = root;
        TreeNode p = null;
        while (cur != null) {
            if (val > cur.val) {
                p = cur;
                cur = cur.right;
            }else if (val < cur.val) {
                p = cur;
                cur = cur.left;
            }else {
                return;
            }
            if (cur == null) {
                if (val < p.val) {
                    p.left = node;
                }else {
                    p.right = node;
                }
            }
        }
    }
    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //删除
    public void remove(int val) {
        TreeNode cur = root;
        TreeNode p = null;
        while (cur != null) {
            if (cur.val == val) {
                removeNode(p,cur);
                return;
            }else if (cur.val < val) {
                p = cur;
                cur = cur.right;
            }else {
                p = cur;
                cur = cur.left;
            }
        }
    }
    private void removeNode(TreeNode p, TreeNode cur) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            }else if (p.left == cur) {
                p.left = cur.right;
            }else {
                p.right = cur.right;
            }
        }else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            }else if (cur == p.left) {
                p.left = cur.left;
            }else {
                p.right = cur.left;
            }
        }else {
            TreeNode target = cur.right;
            TreeNode targetP = cur;
            while (target.left != null) {
                targetP = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetP.left) {
                targetP.left = target.right;
            }else {
                targetP.right = target.right;
            }

        }
    }
}
